'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-08-13 16:42:59
LastEditTime: 2025-08-13 17:09:37
'''
# @需要再理解和复习
# 寻找重复数


class Solution:

    def findDuplicate(self, nums: list[int]) -> int:

        """
        如果有重复数字x，那么会有多个位置指向同一个位置x
        环的入口就是重复数字
        """

        slow = 0 # 慢指针，每次走一步
        fast = 0 # 快指针，每次走两步
        # 第一阶段
        while True:
            fast = nums[fast]
            fast = nums[fast]

            slow = nums[slow]

            if slow == fast:
                break
        
        # 第二阶段
        ptr = 0

        while ptr != slow:
            ptr = nums[ptr]
            slow = nums[slow]

        
        return ptr



